package day001;

public class Code06_MergeSort {

    public static void mergeSort(int[] arr){
        if(arr == null || arr.length < 2){
            return;
        }

        process(arr, 0, arr.length-1);
    }

    public static void process(int[] arr, int L, int R){
        if(L == R){
            return;
        }
        int mid = L +((R - L) >> 1);
        process(arr,L,mid);
        process(arr,mid+1,R);
        merger(arr, L, mid, R);
    }

    public static void merger(int[] arr, int L, int M, int R){
        int p1 = L;
        int p2 = M + 1;
        int[] temp = new int[R - L + 1];
        int i = 0;

        while(p1 <= M && p2 <= R){
            if(arr[p1] <= arr[p2]){
                temp[i++] = arr[p1++];
            }else{
                temp[i++] = arr[p2++];
            }

        }

        while(p1 <= M){
            temp[i++] = arr[p1++];
        }
        while(p2 <= R){
            temp[i++] = arr[p2++];
        }

        for(int j = 0;j < temp.length;j++) {
            arr[j + L] = temp[j];
        }
    }

    public static void main(String[] args) {
        int[] arr = {4,2,3,2,6,5};
        mergeSort(arr);
        for(int a : arr){
            System.out.print(a);
        }
    }


}
